package g2Solution;
import java.util.*;

import redBlackTree.RedBlackTree;
import g2RedBlackTree.*;

public class MySolution {
	public String Qc(MobiTTree root, String key){
		ArrayList<MyNode<String>> path ;
		path = root.findPath(key);
		if (path == null){
			return "not found";
		}
		int n = path.size();
		int [] level = new int[n];
		int [] h = new int[n];
		int i = 0;
		
		level[n-1] = 0;
		h[n-1] = 0;
		for(i = n - 2; i >= 0; i--){
			
			MyNode<String> current = path.get(i);
			MyNode<String> child = path.get(i+1);
			if (current.isLeftSubTree(child)){
				level[i] = current.rightLevel();
			} else {
				level[i] = current.leftLevel();
			}
			h[i] = level[i] + n - i - 1;
		}
		int max = maxArray(h);
		MyNode<String> currenttmp = path.get(n-1);
		if (max < currenttmp.leftLevel()){
			max = currenttmp.leftLevel();
		}
		if (max < currenttmp.rightLevel()){
			max = currenttmp.rightLevel();
		}
		String result = "";
		ArrayList<MyNode<String>> resultlist = new ArrayList<MyNode<String>>();
		for(i = 0; i < n-1; i++){
			if (h[i] == max){
				MyNode<String> current = path.get(i);
				if (current.isLeftSubTree(path.get(i+1))){
					root.getLeafWithRightLevel(current, level[i], resultlist);
				}
				else {
					root.getLeafWithLeftLevel(current, level[i], resultlist);
				}
			}
		}
		if (max == currenttmp.leftLevel()){
			root.getLeafWithRightLevel(currenttmp, max, resultlist);
		}
		if (max == currenttmp.rightLevel()){
			root.getLeafWithRightLevel(currenttmp, max, resultlist);
		}
		for(MyNode<String> current : resultlist){
			@SuppressWarnings("unchecked")
			RedBlackNodeData<String, DataTTree> tmp = (RedBlackNodeData<String, DataTTree>) current;
			
			result += tmp.getWords();
		}
		
		return result;
	}
	
	public void printArray(int[] arr){
		for(int a: arr){
			System.out.print(a);
			System.out.print(" ");
		}
		System.out.println();
	}
	public int maxArray(int [] arr){
		int max = 0;
		for(int a: arr){
			if (a > max){
				max = a;
			}
		}
		return max;
	}
	public String Qb(MobiTTree root, String n1, String n2){
		ArrayList<MyNode<String>> path1 = new ArrayList<MyNode<String>>();
		ArrayList<MyNode<String>> path2 = new ArrayList<MyNode<String>>();
		path1 = root.findPath(n1 );
		path2 = root.findPath(n2);
		return printPathN2N(path1, path2);
	}
	public void printPath(ArrayList<MyNode<String>> path){
		if (path == null){
			return;
		}
		for(MyNode<String> c : path){
			System.out.print(c);
			System.out.print(",");
		}
		System.out.println();
	}
	private String printPathN2N(ArrayList<MyNode<String>> path1, ArrayList<MyNode<String>> path2){
		ArrayList<MyNode<String>> resultpath = new ArrayList<MyNode<String>>();
		resultpath = mergePathN2N(path1, path2);
		if (resultpath == null){
			return "";
		}
		String result = "";
		
		for(MyNode<String> a: resultpath){
			result += a + " ";
		}
		return result;
	}
	private ArrayList<MyNode<String>>  mergePathN2N(ArrayList<MyNode<String>> path1, ArrayList<MyNode<String>> path2){
		
		if (path1 == null && path2 == null){
			return null;
		}
		ArrayList<MyNode<String>> result = new ArrayList<MyNode<String>> ();
		int i = 0;
		int n = Math.min(path1.size(), path2.size());
		boolean found = false;
		while (!found){
			if(MobiTTree.compareTo(path1.get(i), path2.get(i)) != 0){
				found = true;
				
			}else {
				i++;
			}
			if (i >= n){
				break;
			}
			
		}
		int j = 0;
		System.out.println(i);
		for(j = path1.size()-1; j >= i; j-- ){
			result.add(path1.get(j));
		}
		for(j = i-1; j < path2.size(); j++ ){
			result.add(path2.get(j));
		}
		return result;
		
	}
	
	
}
